#include "levenshtein.h"

#include <vector>

using std::vector;

inline int min(int a, int b, int c)
{
    int result = a < b ? a: b;
    result = result < c ? result : c;
    return result;
}

typedef std::string::const_iterator iterator;
int levenshtein_r(iterator fBegin, iterator fEnd, iterator sBegin, iterator sEnd)
{
    if ((fBegin == fEnd) && (sBegin == sEnd))
        return 0;

    if (fBegin == fEnd)
        return (sEnd - sBegin);

    if (sBegin == sEnd)
        return (fEnd - fBegin);

    const iterator fLastChar = fEnd - 1;
    const iterator sLastChar = sEnd - 1;

    int ifRemove1 = levenshtein_r(fBegin, fLastChar , sBegin, sEnd) + 1;
    int ifRemove2 = levenshtein_r(fBegin, fEnd, sBegin, sLastChar) + 1;
    int ifReplace = levenshtein_r(fBegin, fLastChar, sBegin, sLastChar);
    
    if ((*fLastChar) != (*sLastChar))
        ++ifReplace;

    return min(ifRemove1, ifRemove2, ifReplace);
}

int levenshtein_table(const std::string& first, const std::string& second)
{
    const int height = first.length() + 1;
    const int width = second.length() + 1;

    vector<int> table(width*height);

    for (int i = 0; i < height; ++i)
        table[i*width] = i;

    for (int j = 0; j < width; ++j)
        table[j] = j;

    for (int i = 1; i < height; ++i)
    {
        for (int j = 1; j < width; ++j)
        {
            int ifReplace = table[(i-1)*width + j-1];
            if (first[i-1] != second[j-1])
                ++ifReplace;
    
            table[i*width + j] = min(ifReplace, 
                                     table[i*width + j-1] + 1,
                                     table[(i-1)*width + j] + 1);
        }
    }

    return table[width*height - 1];
}

int levenshtein_distance(const std::string& first, const std::string& second)
{
    return levenshtein_table(first, second);
}
